首先有一个非常 naive 的 dp。
令 表示到第 座岛的最大收益，那么有：
然后你按坐标排序，遇到纵坐标大于当前岛的直接剪掉。
这样就有 60 pts 了。
因为有坐标限制所以不好优化，考虑另一种 。
令 表示走到 的最大收益，如果没有岛为极小值。
那么转移为：
这样我们就成功把 优化转换为 了。
这是一个二维斜率优化，令 优于 ，那么有：
An Ac a day, keeps the doctor away!
Chihik's Blog
首先有一个非常 naive 的 O(n2) dp。
令 dpi 表示到第 i 座岛的最大收益，那么有：
dpi=1≤j≤n,j=i,xj≤xi,yj≤yimax{dpj−(xi−xj)2−(yi−yj)2}+vi
然后你按坐标排序，遇到纵坐标大于当前岛的直接剪掉。
这样就有 60 pts 了。
因为有坐标限制所以不好优化，考虑另一种 dp。
令 dpi,j 表示走到 (i,j) 的最大收益，如果没有岛为极小值。
那么转移为：
dpi,j=1≤k≤i,1≤l≤jmax{dpk,l+(i−k)2+(j−l)2}+vi,j
dpi,j=1≤k≤i,1≤l≤jmax{dpk,l+k2−2ik+l2−2jl}+vi,j+i2+j2
这样我们就成功把 O(n2) 优化转换为 O(m4) 了。
这是一个二维斜率优化，令 (j1,j2) 优于 (k1,k2) ，那么有：
dpj1,j2+j12−2ij1+j22−2jj2<dpk1,k2+k12−2ik1+k22−2jk2
(dpj1,j2+j12+j22)−(dpk1,k2+k12+k22)<2i(j1−k1)+2j(j2−k2)
扫码打赏，你说多少就多少
打开微信扫一扫，即可进行扫码打赏哦